package arrays;

import java.util.HashMap;
import java.util.Map;

/**
 * @author pengfei.hpf
 * @date 2020/3/13
 * @verdion 1.0.0
 * 169. 多数元素
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 * 示例 1:
 *
 * 输入: [3,2,3]
 * 输出: 3
 * 示例 2:
 *
 * 输入: [2,2,1,1,1,2,2]
 * 输出: 2
 */
public class MajorityElement {
    public int majorityElement(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        int len = nums.length /2;
        for(int i = 0; i < nums.length; i ++){
            int count = map.getOrDefault(nums[i], 0);
            count ++;
            if(count > len){
                return nums[i];
            }
            map.put(nums[i], count);
        }
        return 0;
    }
}
